/*-------------------------------------------------------------------------
 *
 * tsgistidx.c
 *	  GiST 支持函数 tsvector_ops
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/tsgistidx.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/gist.h"
#include "access/heaptoast.h"
#include "access/reloptions.h"
#include "lib/qunique.h"
#include "port/pg_bitutils.h"
#include "tsearch/ts_utils.h"
#include "utils/builtins.h"
#include "utils/pg_crc.h"


/* tsvector_ops 操作类选项 */
typedef struct
{
	int32		vl_len_;		/* varlena 头部（请勿直接触摸！） */
	int			siglen;			/* 签名长度 */
} GistTsVectorOptions;

#define SIGLEN_DEFAULT	(31 * 4)
#define SIGLEN_MAX		GISTMaxIndexKeySize
#define GET_SIGLEN()	(PG_HAS_OPCLASS_OPTIONS() ? \
						 ((GistTsVectorOptions *) PG_GET_OPCLASS_OPTIONS())->siglen : \
						 SIGLEN_DEFAULT)

#define SIGLENBIT(siglen) ((siglen) * BITS_PER_BYTE)

typedef char *BITVECP;

#define LOOPBYTE(siglen) \
			for (i = 0; i < siglen; i++)

#define GETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
#define GETBITBYTE(x,i) ( ((char)(x)) >> (i) & 0x01 )
#define CLRBIT(x,i)   GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITS_PER_BYTE ) )
#define SETBIT(x,i)   GETBYTE(x,i) |=  ( 0x01 << ( (i) % BITS_PER_BYTE ) )
#define GETBIT(x,i) ( (GETBYTE(x,i) >> ( (i) % BITS_PER_BYTE )) & 0x01 )

#define HASHVAL(val, siglen) (((unsigned int)(val)) % SIGLENBIT(siglen))
#define HASH(sign, val, siglen) SETBIT((sign), HASHVAL(val, siglen))

#define GETENTRY(vec,pos) ((SignTSVector *) DatumGetPointer((vec)->vector[(pos)].key))

/*
 * GiST 索引键的类型
 */

typedef struct
{
	int32		vl_len_;		/* varlena 头部（请勿直接触摸！） */
	int32		flag;
	char		data[FLEXIBLE_ARRAY_MEMBER];
} SignTSVector;

#define ARRKEY		0x01
#define SIGNKEY		0x02
#define ALLISTRUE	0x04

#define ISARRKEY(x) ( ((SignTSVector*)(x))->flag & ARRKEY )
#define ISSIGNKEY(x)	( ((SignTSVector*)(x))->flag & SIGNKEY )
#define ISALLTRUE(x)	( ((SignTSVector*)(x))->flag & ALLISTRUE )

#define GTHDRSIZE	( VARHDRSZ + sizeof(int32) )
#define CALCGTSIZE(flag, len) ( GTHDRSIZE + ( ( (flag) & ARRKEY ) ? ((len)*sizeof(int32)) : (((flag) & ALLISTRUE) ? 0 : (len)) ) )

#define GETSIGN(x)	( (BITVECP)( (char*)(x)+GTHDRSIZE ) )
#define GETSIGLEN(x)( VARSIZE(x) - GTHDRSIZE )
#define GETARR(x)	( (int32*)( (char*)(x)+GTHDRSIZE ) )
#define ARRNELEM(x) ( ( VARSIZE(x) - GTHDRSIZE )/sizeof(int32) )

static int32 fc_sizebitvec(BITVECP fc_sign, int fc_siglen);

Datum gtsvectorin(PG_FUNCTION_ARGS)
{
	ereport(ERROR,
			(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
			 errmsg("gtsvector_in not implemented")));
	PG_RETURN_DATUM(0);
}

#define SINGOUTSTR	"%d true bits, %d false bits"
#define ARROUTSTR	"%d unique words"
#define EXTRALEN	( 2*13 )

static int	outbuf_maxlen = 0;

Datum gtsvectorout(PG_FUNCTION_ARGS)
{
	SignTSVector *fc_key = (SignTSVector *) PG_DETOAST_DATUM(PG_GETARG_POINTER(0));
	char	   *fc_outbuf;

	if (outbuf_maxlen == 0)
		outbuf_maxlen = 2 * EXTRALEN + Max(strlen(SINGOUTSTR), strlen(ARROUTSTR)) + 1;
	fc_outbuf = palloc(outbuf_maxlen);

	if (ISARRKEY(fc_key))
		sprintf(fc_outbuf, ARROUTSTR, (int) ARRNELEM(fc_key));
	else
	{
		int			fc_siglen = GETSIGLEN(fc_key);
		int			fc_cnttrue = (ISALLTRUE(fc_key)) ? SIGLENBIT(fc_siglen) : fc_sizebitvec(GETSIGN(fc_key), fc_siglen);

		sprintf(fc_outbuf, SINGOUTSTR, fc_cnttrue, (int) SIGLENBIT(fc_siglen) - fc_cnttrue);
	}

	PG_FREE_IF_COPY(fc_key, 0);
	PG_RETURN_POINTER(fc_outbuf);
}

static int fc_compareint(const void *fc_va, const void *fc_vb)
{
	int32		fc_a = *((const int32 *) fc_va);
	int32		fc_b = *((const int32 *) fc_vb);

	if (fc_a == fc_b)
		return 0;
	return (fc_a > fc_b) ? 1 : -1;
}

static void fc_makesign(BITVECP fc_sign, SignTSVector *fc_a, int fc_siglen)
{
	int32		fc_k,
				fc_len = ARRNELEM(fc_a);
	int32	   *fc_ptr = GETARR(fc_a);

	MemSet((void *) fc_sign, 0, fc_siglen);
	for (fc_k = 0; fc_k < fc_len; fc_k++)
		HASH(fc_sign, fc_ptr[fc_k], fc_siglen);
}

static SignTSVector *
fc_gtsvector_alloc(int fc_flag, int fc_len, BITVECP fc_sign)
{
	int			fc_size = CALCGTSIZE(fc_flag, fc_len);
	SignTSVector *fc_res = palloc(fc_size);

	SET_VARSIZE(fc_res, fc_size);
	fc_res->flag = fc_flag;

	if ((fc_flag & (SIGNKEY | ALLISTRUE)) == SIGNKEY && fc_sign)
		memcpy(GETSIGN(fc_res), fc_sign, fc_len);

	return fc_res;
}


Datum gtsvector_compress(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	int			fc_siglen = GET_SIGLEN();
	GISTENTRY  *fc_retval = fc_entry;

	if (fc_entry->leafkey)
	{							/* tsvector */
		TSVector	fc_val = DatumGetTSVector(fc_entry->key);
		SignTSVector *fc_res = fc_gtsvector_alloc(ARRKEY, fc_val->size, NULL);
		int32		fc_len;
		int32	   *fc_arr;
		WordEntry  *fc_ptr = ARRPTR(fc_val);
		char	   *fc_words = STRPTR(fc_val);

		fc_arr = GETARR(fc_res);
		fc_len = fc_val->size;
		while (fc_len--)
		{
			pg_crc32	fc_c;

			INIT_LEGACY_CRC32(fc_c);
			COMP_LEGACY_CRC32(fc_c, fc_words + fc_ptr->pos, fc_ptr->len);
			FIN_LEGACY_CRC32(fc_c);

			*fc_arr = *(int32 *) &fc_c;
			fc_arr++;
			fc_ptr++;
		}

		qsort(GETARR(fc_res), fc_val->size, sizeof(int), fc_compareint);
		fc_len = qunique(GETARR(fc_res), fc_val->size, sizeof(int), fc_compareint);
		if (fc_len != fc_val->size)
		{
			/*
			 * 哈希函数发生碰撞；len总是小于
			 * val->size
			 */
			fc_len = CALCGTSIZE(ARRKEY, fc_len);
			fc_res = (SignTSVector *) repalloc((void *) fc_res, fc_len);
			SET_VARSIZE(fc_res, fc_len);
		}

		/* 如果数组太长，则创建签名 */
		if (VARSIZE(fc_res) > TOAST_INDEX_TARGET)
		{
			SignTSVector *fc_ressign = fc_gtsvector_alloc(SIGNKEY, fc_siglen, NULL);

			fc_makesign(GETSIGN(fc_ressign), fc_res, fc_siglen);
			fc_res = fc_ressign;
		}

		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	else if (ISSIGNKEY(DatumGetPointer(fc_entry->key)) &&
			 !ISALLTRUE(DatumGetPointer(fc_entry->key)))
	{
		int32		i;
		SignTSVector *fc_res;
		BITVECP		fc_sign = GETSIGN(DatumGetPointer(fc_entry->key));

		LOOPBYTE(fc_siglen)
		{
			if ((fc_sign[i] & 0xff) != 0xff)
				PG_RETURN_POINTER(fc_retval);
		}

		fc_res = fc_gtsvector_alloc(SIGNKEY | ALLISTRUE, fc_siglen, fc_sign);
		fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));
		gistentryinit(*fc_retval, PointerGetDatum(fc_res),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);
	}
	PG_RETURN_POINTER(fc_retval);
}

Datum gtsvector_decompress(PG_FUNCTION_ARGS)
{
	/*
	 * 我们需要解除蒸发存储的值，因为其他gtsvector
	 * 支持函数无法处理已蒸发的值。
	 */
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	SignTSVector *fc_key = (SignTSVector *) PG_DETOAST_DATUM(fc_entry->key);

	if (fc_key != (SignTSVector *) DatumGetPointer(fc_entry->key))
	{
		GISTENTRY  *fc_retval = (GISTENTRY *) palloc(sizeof(GISTENTRY));

		gistentryinit(*fc_retval, PointerGetDatum(fc_key),
					  fc_entry->rel, fc_entry->page,
					  fc_entry->offset, false);

		PG_RETURN_POINTER(fc_retval);
	}

	PG_RETURN_POINTER(fc_entry);
}

typedef struct
{
	int32	   *arrb;
	int32	   *arre;
} CHKVAL;

/*
 * TS_execute 回调，用于将 tsquery 操作数与 GIST 叶页面数据匹配
 */
static TSTernaryValue fc_checkcondition_arr(void *fc_checkval, QueryOperand *fc_val, ExecPhraseData *fc_data)
{
	int32	   *fc_StopLow = ((CHKVAL *) fc_checkval)->arrb;
	int32	   *fc_StopHigh = ((CHKVAL *) fc_checkval)->arre;
	int32	   *fc_StopMiddle;

	/* 循环不变式： StopLow <= val < StopHigh */

	/*
	 * 我们无法通过哈希值找到前缀
	 */
	if (fc_val->prefix)
		return TS_MAYBE;

	while (fc_StopLow < fc_StopHigh)
	{
		fc_StopMiddle = fc_StopLow + (fc_StopHigh - fc_StopLow) / 2;
		if (*fc_StopMiddle == fc_val->valcrc)
			return TS_MAYBE;
		else if (*fc_StopMiddle < fc_val->valcrc)
			fc_StopLow = fc_StopMiddle + 1;
		else
			fc_StopHigh = fc_StopMiddle;
	}

	return TS_NO;
}

/*
 * TS_execute 回调，用于将 tsquery 操作数与 GIST 非叶数据匹配
 */
static TSTernaryValue fc_checkcondition_bit(void *fc_checkval, QueryOperand *fc_val, ExecPhraseData *fc_data)
{
	void	   *fc_key = (SignTSVector *) fc_checkval;

	/*
	 * 我们无法在签名树中找到前缀
	 */
	if (fc_val->prefix)
		return TS_MAYBE;

	if (GETBIT(GETSIGN(fc_key), HASHVAL(fc_val->valcrc, GETSIGLEN(fc_key))))
		return TS_MAYBE;
	else
		return TS_NO;
}

Datum gtsvector_consistent(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_entry = (GISTENTRY *) PG_GETARG_POINTER(0);
	TSQuery		fc_query = PG_GETARG_TSQUERY(1);

	/* StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); */
	/* Oid		subtype = PG_GETARG_OID(3); */
	bool	   *fc_recheck = (bool *) PG_GETARG_POINTER(4);
	SignTSVector *fc_key = (SignTSVector *) DatumGetPointer(fc_entry->key);

	/* 此函数处理的所有情况都是不准确的 */
	*fc_recheck = true;

	if (!fc_query->size)
		PG_RETURN_BOOL(false);

	if (ISSIGNKEY(fc_key))
	{
		if (ISALLTRUE(fc_key))
			PG_RETURN_BOOL(true);

		PG_RETURN_BOOL(TS_execute(GETQUERY(fc_query),
								  fc_key,
								  TS_EXEC_PHRASE_NO_POS,
								  fc_checkcondition_bit));
	}
	else
	{							/* 仅叶页面 */
		CHKVAL		fc_chkval;

		fc_chkval.arrb = GETARR(fc_key);
		fc_chkval.arre = fc_chkval.arrb + ARRNELEM(fc_key);
		PG_RETURN_BOOL(TS_execute(GETQUERY(fc_query),
								  (void *) &fc_chkval,
								  TS_EXEC_PHRASE_NO_POS,
								  fc_checkcondition_arr));
	}
}

static int32 fc_unionkey(BITVECP fc_sbase, SignTSVector *fc_add, int fc_siglen)
{
	int32		i;

	if (ISSIGNKEY(fc_add))
	{
		BITVECP		fc_sadd = GETSIGN(fc_add);

		if (ISALLTRUE(fc_add))
			return 1;

		Assert(GETSIGLEN(fc_add) == fc_siglen);

		LOOPBYTE(fc_siglen)
			fc_sbase[i] |= fc_sadd[i];
	}
	else
	{
		int32	   *fc_ptr = GETARR(fc_add);

		for (i = 0; i < ARRNELEM(fc_add); i++)
			HASH(fc_sbase, fc_ptr[i], fc_siglen);
	}
	return 0;
}


Datum gtsvector_union(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	int		   *fc_size = (int *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	SignTSVector *fc_result = fc_gtsvector_alloc(SIGNKEY, fc_siglen, NULL);
	BITVECP		fc_base = GETSIGN(fc_result);
	int32		i;

	memset(fc_base, 0, fc_siglen);

	for (i = 0; i < fc_entryvec->n; i++)
	{
		if (fc_unionkey(fc_base, GETENTRY(fc_entryvec, i), fc_siglen))
		{
			fc_result->flag |= ALLISTRUE;
			SET_VARSIZE(fc_result, CALCGTSIZE(fc_result->flag, fc_siglen));
			break;
		}
	}

	*fc_size = VARSIZE(fc_result);

	PG_RETURN_POINTER(fc_result);
}

Datum gtsvector_same(PG_FUNCTION_ARGS)
{
	SignTSVector *fc_a = (SignTSVector *) PG_GETARG_POINTER(0);
	SignTSVector *fc_b = (SignTSVector *) PG_GETARG_POINTER(1);
	bool	   *fc_result = (bool *) PG_GETARG_POINTER(2);
	int			fc_siglen = GET_SIGLEN();

	if (ISSIGNKEY(fc_a))
	{							/* 那么b也也是ISSIGNKEY */
		if (ISALLTRUE(fc_a) && ISALLTRUE(fc_b))
			*fc_result = true;
		else if (ISALLTRUE(fc_a))
			*fc_result = false;
		else if (ISALLTRUE(fc_b))
			*fc_result = false;
		else
		{
			int32		i;
			BITVECP		fc_sa = GETSIGN(fc_a),
						fc_sb = GETSIGN(fc_b);

			Assert(GETSIGLEN(fc_a) == fc_siglen && GETSIGLEN(fc_b) == fc_siglen);

			*fc_result = true;
			LOOPBYTE(fc_siglen)
			{
				if (fc_sa[i] != fc_sb[i])
				{
					*fc_result = false;
					break;
				}
			}
		}
	}
	else
	{							/* a和b是ISARRKEY */
		int32		fc_lena = ARRNELEM(fc_a),
					fc_lenb = ARRNELEM(fc_b);

		if (fc_lena != fc_lenb)
			*fc_result = false;
		else
		{
			int32	   *fc_ptra = GETARR(fc_a),
					   *fc_ptrb = GETARR(fc_b);
			int32		i;

			*fc_result = true;
			for (i = 0; i < fc_lena; i++)
				if (fc_ptra[i] != fc_ptrb[i])
				{
					*fc_result = false;
					break;
				}
		}
	}

	PG_RETURN_POINTER(fc_result);
}

static int32 fc_sizebitvec(BITVECP fc_sign, int fc_siglen)
{
	return pg_popcount(fc_sign, fc_siglen);
}

static int hemdistsign(BITVECP a, BITVECP b, int siglen)
{
	int			i,
				diff,
				dist = 0;

	LOOPBYTE(siglen)
	{
		diff = (unsigned char) (a[i] ^ b[i]);
		/* 在这里使用 popcount 函数不太可能获胜 */
		dist += pg_number_of_ones[diff];
	}
	return dist;
}

static int fc_hemdist(SignTSVector *fc_a, SignTSVector *fc_b)
{
	int			fc_siglena = GETSIGLEN(fc_a);
	int			fc_siglenb = GETSIGLEN(fc_b);

	if (ISALLTRUE(fc_a))
	{
		if (ISALLTRUE(fc_b))
			return 0;
		else
			return SIGLENBIT(fc_siglenb) - fc_sizebitvec(GETSIGN(fc_b), fc_siglenb);
	}
	else if (ISALLTRUE(fc_b))
		return SIGLENBIT(fc_siglena) - fc_sizebitvec(GETSIGN(fc_a), fc_siglena);

	Assert(fc_siglena == fc_siglenb);

	return hemdistsign(GETSIGN(fc_a), GETSIGN(fc_b), fc_siglena);
}

Datum gtsvector_penalty(PG_FUNCTION_ARGS)
{
	GISTENTRY  *fc_origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* 始终 ISSIGNKEY */
	GISTENTRY  *fc_newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
	float	   *fc_penalty = (float *) PG_GETARG_POINTER(2);
	int			fc_siglen = GET_SIGLEN();
	SignTSVector *fc_origval = (SignTSVector *) DatumGetPointer(fc_origentry->key);
	SignTSVector *fc_newval = (SignTSVector *) DatumGetPointer(fc_newentry->key);
	BITVECP		fc_orig = GETSIGN(fc_origval);

	*fc_penalty = 0.0;

	if (ISARRKEY(fc_newval))
	{
		BITVECP		fc_sign = palloc(fc_siglen);

		fc_makesign(fc_sign, fc_newval, fc_siglen);

		if (ISALLTRUE(fc_origval))
		{
			int			fc_siglenbit = SIGLENBIT(fc_siglen);

			*fc_penalty =
				(float) (fc_siglenbit - fc_sizebitvec(fc_sign, fc_siglen)) /
				(float) (fc_siglenbit + 1);
		}
		else
			*fc_penalty = hemdistsign(fc_sign, fc_orig, fc_siglen);

		pfree(fc_sign);
	}
	else
		*fc_penalty = fc_hemdist(fc_origval, fc_newval);
	PG_RETURN_POINTER(fc_penalty);
}

typedef struct
{
	bool		allistrue;
	BITVECP		sign;
} CACHESIGN;

static void fc_fillcache(CACHESIGN *fc_item, SignTSVector *fc_key, int fc_siglen)
{
	fc_item->allistrue = false;
	if (ISARRKEY(fc_key))
		fc_makesign(fc_item->sign, fc_key, fc_siglen);
	else if (ISALLTRUE(fc_key))
		fc_item->allistrue = true;
	else
		memcpy((void *) fc_item->sign, (void *) GETSIGN(fc_key), fc_siglen);
}

#define WISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
typedef struct
{
	OffsetNumber pos;
	int32		cost;
} SPLITCOST;

static int fc_comparecost(const void *fc_va, const void *fc_vb)
{
	const SPLITCOST *fc_a = (const SPLITCOST *) fc_va;
	const SPLITCOST *fc_b = (const SPLITCOST *) fc_vb;

	if (fc_a->cost == fc_b->cost)
		return 0;
	else
		return (fc_a->cost > fc_b->cost) ? 1 : -1;
}


static int fc_hemdistcache(CACHESIGN *fc_a, CACHESIGN *fc_b, int fc_siglen)
{
	if (fc_a->allistrue)
	{
		if (fc_b->allistrue)
			return 0;
		else
			return SIGLENBIT(fc_siglen) - fc_sizebitvec(fc_b->sign, fc_siglen);
	}
	else if (fc_b->allistrue)
		return SIGLENBIT(fc_siglen) - fc_sizebitvec(fc_a->sign, fc_siglen);

	return hemdistsign(fc_a->sign, fc_b->sign, fc_siglen);
}

Datum gtsvector_picksplit(PG_FUNCTION_ARGS)
{
	GistEntryVector *fc_entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
	GIST_SPLITVEC *fc_v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
	int			fc_siglen = GET_SIGLEN();
	OffsetNumber fc_k,
				fc_j;
	SignTSVector *fc_datum_l,
			   *fc_datum_r;
	BITVECP		fc_union_l,
				fc_union_r;
	int32		fc_size_alpha,
				fc_size_beta;
	int32		fc_size_waste,
				fc_waste = -1;
	int32		fc_nbytes;
	OffsetNumber fc_seed_1 = 0,
				fc_seed_2 = 0;
	OffsetNumber *fc_left,
			   *fc_right;
	OffsetNumber fc_maxoff;
	BITVECP		fc_ptr;
	int			i;
	CACHESIGN  *fc_cache;
	char	   *fc_cache_sign;
	SPLITCOST  *fc_costvector;

	fc_maxoff = fc_entryvec->n - 2;
	fc_nbytes = (fc_maxoff + 2) * sizeof(OffsetNumber);
	fc_v->spl_left = (OffsetNumber *) palloc(fc_nbytes);
	fc_v->spl_right = (OffsetNumber *) palloc(fc_nbytes);

	fc_cache = (CACHESIGN *) palloc(sizeof(CACHESIGN) * (fc_maxoff + 2));
	fc_cache_sign = palloc(fc_siglen * (fc_maxoff + 2));

	for (fc_j = 0; fc_j < fc_maxoff + 2; fc_j++)
		fc_cache[fc_j].sign = &fc_cache_sign[fc_siglen * fc_j];

	fc_fillcache(&fc_cache[FirstOffsetNumber], GETENTRY(fc_entryvec, FirstOffsetNumber),
			  fc_siglen);

	for (fc_k = FirstOffsetNumber; fc_k < fc_maxoff; fc_k = OffsetNumberNext(fc_k))
	{
		for (fc_j = OffsetNumberNext(fc_k); fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
		{
			if (fc_k == FirstOffsetNumber)
				fc_fillcache(&fc_cache[fc_j], GETENTRY(fc_entryvec, fc_j), fc_siglen);

			fc_size_waste = fc_hemdistcache(&(fc_cache[fc_j]), &(fc_cache[fc_k]), fc_siglen);
			if (fc_size_waste > fc_waste)
			{
				fc_waste = fc_size_waste;
				fc_seed_1 = fc_k;
				fc_seed_2 = fc_j;
			}
		}
	}

	fc_left = fc_v->spl_left;
	fc_v->spl_nleft = 0;
	fc_right = fc_v->spl_right;
	fc_v->spl_nright = 0;

	if (fc_seed_1 == 0 || fc_seed_2 == 0)
	{
		fc_seed_1 = 1;
		fc_seed_2 = 2;
	}

	/* 形成初始 .. */
	fc_datum_l = fc_gtsvector_alloc(SIGNKEY | (fc_cache[fc_seed_1].allistrue ? ALLISTRUE : 0),
							  fc_siglen, fc_cache[fc_seed_1].sign);
	fc_datum_r = fc_gtsvector_alloc(SIGNKEY | (fc_cache[fc_seed_2].allistrue ? ALLISTRUE : 0),
							  fc_siglen, fc_cache[fc_seed_2].sign);
	fc_union_l = GETSIGN(fc_datum_l);
	fc_union_r = GETSIGN(fc_datum_r);
	fc_maxoff = OffsetNumberNext(fc_maxoff);
	fc_fillcache(&fc_cache[fc_maxoff], GETENTRY(fc_entryvec, fc_maxoff), fc_siglen);
	/* 在 ... 之前排序 */
	fc_costvector = (SPLITCOST *) palloc(sizeof(SPLITCOST) * fc_maxoff);
	for (fc_j = FirstOffsetNumber; fc_j <= fc_maxoff; fc_j = OffsetNumberNext(fc_j))
	{
		fc_costvector[fc_j - 1].pos = fc_j;
		fc_size_alpha = fc_hemdistcache(&(fc_cache[fc_seed_1]), &(fc_cache[fc_j]), fc_siglen);
		fc_size_beta = fc_hemdistcache(&(fc_cache[fc_seed_2]), &(fc_cache[fc_j]), fc_siglen);
		fc_costvector[fc_j - 1].cost = Abs(fc_size_alpha - fc_size_beta);
	}
	qsort((void *) fc_costvector, fc_maxoff, sizeof(SPLITCOST), fc_comparecost);

	for (fc_k = 0; fc_k < fc_maxoff; fc_k++)
	{
		fc_j = fc_costvector[fc_k].pos;
		if (fc_j == fc_seed_1)
		{
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
			continue;
		}
		else if (fc_j == fc_seed_2)
		{
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
			continue;
		}

		if (ISALLTRUE(fc_datum_l) || fc_cache[fc_j].allistrue)
		{
			if (ISALLTRUE(fc_datum_l) && fc_cache[fc_j].allistrue)
				fc_size_alpha = 0;
			else
				fc_size_alpha = SIGLENBIT(fc_siglen) -
					fc_sizebitvec((fc_cache[fc_j].allistrue) ?
							   GETSIGN(fc_datum_l) :
							   fc_cache[fc_j].sign,
							   fc_siglen);
		}
		else
			fc_size_alpha = hemdistsign(fc_cache[fc_j].sign, GETSIGN(fc_datum_l), fc_siglen);

		if (ISALLTRUE(fc_datum_r) || fc_cache[fc_j].allistrue)
		{
			if (ISALLTRUE(fc_datum_r) && fc_cache[fc_j].allistrue)
				fc_size_beta = 0;
			else
				fc_size_beta = SIGLENBIT(fc_siglen) -
					fc_sizebitvec((fc_cache[fc_j].allistrue) ?
							   GETSIGN(fc_datum_r) :
							   fc_cache[fc_j].sign,
							   fc_siglen);
		}
		else
			fc_size_beta = hemdistsign(fc_cache[fc_j].sign, GETSIGN(fc_datum_r), fc_siglen);

		if (fc_size_alpha < fc_size_beta + WISH_F(fc_v->spl_nleft, fc_v->spl_nright, 0.1))
		{
			if (ISALLTRUE(fc_datum_l) || fc_cache[fc_j].allistrue)
			{
				if (!ISALLTRUE(fc_datum_l))
					MemSet((void *) GETSIGN(fc_datum_l), 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = fc_cache[fc_j].sign;
				LOOPBYTE(fc_siglen)
					fc_union_l[i] |= fc_ptr[i];
			}
			*fc_left++ = fc_j;
			fc_v->spl_nleft++;
		}
		else
		{
			if (ISALLTRUE(fc_datum_r) || fc_cache[fc_j].allistrue)
			{
				if (!ISALLTRUE(fc_datum_r))
					MemSet((void *) GETSIGN(fc_datum_r), 0xff, fc_siglen);
			}
			else
			{
				fc_ptr = fc_cache[fc_j].sign;
				LOOPBYTE(fc_siglen)
					fc_union_r[i] |= fc_ptr[i];
			}
			*fc_right++ = fc_j;
			fc_v->spl_nright++;
		}
	}

	*fc_right = *fc_left = FirstOffsetNumber;
	fc_v->spl_ldatum = PointerGetDatum(fc_datum_l);
	fc_v->spl_rdatum = PointerGetDatum(fc_datum_r);

	PG_RETURN_POINTER(fc_v);
}

/*
 * 以前，gtsvector_consistent 在 pg_proc.h 中被声明，
 * 其参数与 GiST 支持函数的文档规范不匹配。
 * 我们修复了这个问题，但我们仍然需要一个具有旧签名的 pg_proc 条目
 * 以支持重新加载9.6之前的 contrib/tsearch2 操作类声明。
 * 这个兼容性函数最终应该被移除。
 */
Datum gtsvector_consistent_oldsig(PG_FUNCTION_ARGS)
{
	return gtsvector_consistent(fcinfo);
}

Datum gtsvector_options(PG_FUNCTION_ARGS)
{
	local_relopts *fc_relopts = (local_relopts *) PG_GETARG_POINTER(0);

	init_local_reloptions(fc_relopts, sizeof(GistTsVectorOptions));
	add_local_int_reloption(fc_relopts, "siglen", "signature length",
							SIGLEN_DEFAULT, 1, SIGLEN_MAX,
							offsetof(GistTsVectorOptions, siglen));

	PG_RETURN_VOID();
}
